package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         1143,
		Discription: "最长公共子序列",
		Level:       2,
		Labels: map[string]int{
			"动态规划":  1,
		},
	})
}

func LongestCommonSubsequence(text1 string, text2 string) int {
	m := len(text1)
	n := len(text2)
	//dp[i:j]表示s1[:i] s2[:j]的最长公共子序列的长度
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
            //如果s1[i-1] s2[j-1]不相等，表示在最长公共序列匹配时，用到了s1[i-1]也用不到s2[j-1]，既等于dp[i][j-1]
			//用到了s1[j-1]也用不到s2[i-1]，既等于dp[i-1][j]
			//取两者最大
			dp[i][j] = max(dp[i][j-1], dp[i-1][j])
			if text1[i-1] == text2[j-1] {
				dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
			}
		}
	}

	return dp[m][n]
}